class Solution {
    // 暴力枚举
    // public int reversePairs(int[] record) {
    //     int count = 0;
    //     for (int i = 0; i < record.length; i++) {
    //         for (int j = i+1; j < record.length; j++) {
    //             if (record[i] > record[j]) {
    //                 count++;
    //             }
    //         }
    //     }
    //     return count;
    // }

    int[] temp;
    public int reversePairs(int[] record) {
        int len = record.length;
        temp = new int[len];
        // 在归并的过程中就统计
        return merge_sort(record, 0, len-1);
    }

    private int merge_sort(int[] nums, int start, int end) {
        if (start >= end) {
            return 0; // 不存在逆序对
        }
        // 递归
        int mid = (start + end) / 2;
        int ret = 0;
        ret += merge_sort(nums, start, mid);
        ret += merge_sort(nums, mid+1, end);
        // 合并：过程中进行排序并计算
        // 统计
        int left = start, right = mid+1, i = 0;
        while (left <= mid && right <= end) {
            if (nums[left] <= nums[right]) {
                temp[i++] = nums[left++];
            } else {
                ret += (mid-left+1);
                temp[i++] = nums[right++];
            }
        }
        while (left <= mid) {
            temp[i++] = nums[left++];
        }
        while (right <= end) {
            temp[i++] = nums[right++];
        }
        // 排序
        for (int j = start; j <= end; j++) {
            nums[j] = temp[j-start];
        }
        return ret;
    }
}